<head>
  <meta http-equiv="Content-Type" content="text/html; charset=utf-8" />
<title>План лекций</title>
  <link href=styles/styles.css rel="stylesheet" type="text/css">
</head>
<h2>Дерево отрезков. Начало.</h2>
<ol>
  <li>Массив не меняется</li>
  <ol>
    <li>Частичные суммы</li>
    <li>Частичные минимумы</li>
    <li>Задача: найти подотрезок максимальной суммы, длины хотя бы k</li>
  </ol></li>
  <li>Дерево отрезков снизу</li>
  <ol>
    <li>Хранение: листья нумеруются с 2<sup>k</sup>, корень = 1, i &rarr; 2i, 2i+1, i/2</li>
    <li>Сумма на отрезке, минимум на отрезке: O(log(R-L)) времени</li>
    <li>Изменение в точке: O(logN) времени.</li>
    <li>Модификация дерево, требующая ровно 2n памяти.</li>
    <li>Задача на сжатие координат: a[i]++, сумма на [L..R], 1 &le; i, L, R &le; 10<sup>9</sup>, запросов 10<sup>5</sup></li>
  </ol></li>
  <li>Дерево отрезков сверху</li>
  <ol>
    <li>Хранение</li>
    <li>Динамическое дерево отрезков: O(N &times; logM) памяти</li>
    <li>Сумма и минимум на отрезке, изменение в точке</li>
    <li>Модификации на отрезке</li>
    <ol>
      <li>+= на отрезке, операция сумма</li>
      <li>+= на отрезке, операция минимум</li>
      <li>= на отрезке, операция сумма</li>
      <li>= на отрезке, операция минимум</li>
    </ol></li>
  </ol></li>
</ol>
